//n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：n = 4
//输出：2
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
// 
// 
// Related Topics 回溯 👍 371 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

class NQueensIi {
    public static void main(String[] args) {
        Solution solution = new NQueensIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int totalNQueens(int n) {
            char[][] chessboard = new char[n][n];
            for (int i = 0; i < n; i++) {
                Arrays.fill(chessboard[i], '.');
            }
            backtracking(n, 0, chessboard);
            return result;
        }

        int result = 0;

        public boolean backtracking(int n, int row, char[][] chessboard) {
            if (row == n) {
                result++;
                return true;
            }

            for (int i = 0; i < n; i++) {
                if (isValid(chessboard, n, row, i)) {
                    chessboard[row][i] = 'Q';
                    backtracking(n, row + 1, chessboard);
                    chessboard[row][i] = '.';
                }
            }

            return false;
        }

        public boolean isValid(char[][] chessboard, int n, int row, int col) {
            int i = 0, j = 0;
            for (i = 0; i < row; i++) {
                if (chessboard[i][col] == 'Q') {
                    return false;
                }
            }

            for (i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                if (chessboard[i][j] == 'Q') {
                    return false;
                }
            }

            for (i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                if (chessboard[i][j] == 'Q') {
                    return false;
                }
            }

            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
